\documentclass[submission]{FPSAC2017}

\articlenumber{73}
\addbibresource{73_Gessel_Griffin_Tewari.bib}

%packages
\usepackage[latin1]{inputenc}
\usepackage{float}
\usepackage{amsmath} 
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{latexsym} 
\usepackage{graphicx}
\usepackage{subfigure}
\usepackage{color}
\usepackage{verbatim}
\usepackage[all]{xy}
\usepackage{graphics}
\usepackage{pdfsync}
\usepackage{ytableau}
\usepackage{mathabx} % package added for widecheck

\usepackage[ruled]{algorithm2e}

%% Theorem definitions
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{case}{Case}

\crefname{theorem}{Theorem}{Theorems}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}




\numberwithin{equation}{section}
\setcounter{MaxMatrixCols}{20}


\newcommand{\new}[1]{\ensuremath{\blacktriangleright}#1\ensuremath{\blacktriangleleft}}


%%%%%%blackboard letters
\newcommand{\bC}{\mathbb{C}}
\newcommand{\bN}{\mathbb{N}}
\newcommand{\bK}{\mathbb{K}}
\newcommand{\bP}{\mathbb{Z}_+} 
\newcommand{\bQ}{\mathbb{Q}}
\newcommand{\bR}{\mathbb{R}}
\newcommand{\bZ}{\mathbb{Z}}

%%%%%calligraphic commands%%%%

\newcommand{\cA}{\mathcal{A}}
\newcommand{\cB}{\mathcal{B}}
\newcommand{\cC}{\mathcal{C}}
\newcommand{\cF}{\mathcal{F}}
\newcommand{\cG}{\mathcal{G}}
\newcommand{\cI}{\mathcal{I}}
\newcommand{\cJ}{\mathcal{J}}
\newcommand{\cK}{\mathcal{K}}
\newcommand{\cL}{\mathcal{L}}

%%%%%%%%%%%% posets

\newcommand{\btr}{\blacktriangleright}

%:Sym definitions
\newcommand{\Sym}{\ensuremath{\operatorname{Sym}}}

%:Qsym definitions
\newcommand{\Qsym}{\ensuremath{\operatorname{QSym}}}
\newcommand{\qm}{M}				% monomials

%:Nsym definitions
\newcommand{\Nsym}{\ensuremath{\operatorname{NSym}}}
\newcommand{\nce}{\mathbf{e}}         	% noncommutative elementary fcns
\newcommand{\nch}{\mathbf{h}}         	% noncommutative complete fcns
\newcommand{\ncr}{\mathbf{r}}           	% noncommutative  ribbon schurs
                   




%: compositions and tableaux
\newcommand\ol[1]{\overline{#1}}
\newcommand\ul[1]{\underline{#1}}
\newcommand\ch[1]{\check{#1}}
\newcommand\strongof[1]{{#1}^+}
\newcommand\partitionof[1]{\widetilde{#1}}
\newcommand\reverse[1]{{#1}^r}
\newcommand\ccomplement[1]{{#1}^c}
\newcommand\ctranspose[1]{{#1}^t}

\newcommand{\set}{\mathrm{set}} % for sets corresponding to compositions
\newcommand{\des}{\mathrm{des}} % for descent sets 
\newcommand{\comp}{\mathrm{comp}} % for compositions corresponding to sets
\newcommand{\cont}{\mathrm{cont}} % for content
%\newcommand{\stan}{\mathrm{stan}}% standardization


\newcommand{\refines}{\preccurlyeq}   % for refinement of compositions
\newcommand{\coarsens}{\succcurlyeq}   % for refinement of compositions
\newcommand{\fatzero}{\mathbf{0}}
\newcommand{\suchthat}{\;|\;}

\usepackage{epstopdf}

\usepackage{tikz}

\usetikzlibrary{arrows,petri,topaths}
\usepackage{tkz-berge}
\usepackage{xcolor}
\usetikzlibrary{positioning,arrows,calc,intersections,shapes,decorations}
\newcommand{\st}{\ensuremath{\operatorname{st}}}

% set associated with combinatorial objects
\newcommand{\Asc}{\mathrm{Asc}} % ascent set
\newcommand{\Dsc}{\mathrm{Des}} % descent set
\newcommand{\Exc}{\mathrm{Exc}}  % strong excedance set
\newcommand{\nExc}{\mathrm{nExc}} % not a strong excedance set


% statistics associated with combinatorial objects

\newcommand{\asc}{\mathrm{asc}} % number of ascents
\newcommand{\dsc}{\mathrm{des}} % number of descents
\newcommand{\exc}{\mathrm{exc}}  % number of strong excedance
\newcommand{\nexc}{\mathrm{nexc}} % number of not a strong excedance
\newcommand{\sub}{\mathrm{sub}} % subcedances

% common combinatorial numbers
\newcommand{\Cat}[1]{{\sf Cat}(#1)}% Catalan numbers
\newcommand{\Stir}{{\sf Stir}} % Stirling number of the second kind
\newcommand{\Nar}{{\sf Nar}} % Narayana numbers
\newcommand{\Shi}{\sf Shi} % shi arrangement


% varieties of trees
\newcommand{\rpbt}{\mathcal{RT}} % right-leaning trees
\newcommand{\lbt}{\mathcal{RT}} %    labeled left leaning   binary trees
%\newcommand{\rpbt}{\mathcal{RBT}} %    labeled right-leaning   binary trees
%\newcommand{\ptree}{\mathcal{PT}} %    labeled   k-ary trees

\newcommand{\pbt}{\mathcal{T}} %    labeled   binary trees
\newcommand{\pbtu}{\pbt} % unlabeled
\newcommand{\pbtl}{\pbt^{\ell}} %labeled
\newcommand{\pbtun}{\pbtu_{n}} % unlabeled and exactly n nodes
\newcommand{\pbtln}{\pbtl_{n}} % labeled and exactly n nodes

%\newcommand{\itree}{\mathcal{IT}} % increasing trees
%\newcommand{\iptree}{\mathcal{IPT}} % increasing k-ary trees
%\newcommand{\dtree}{\mathcal{DT}}  %decorated    labeled trees
%\newcommand{\ltree}{\mathcal{LST}} % local search trees
%\newcommand{\riptree}{\mathcal{RPT}} %right increasing   tree

\newcommand{\mbt}{\dot{\pbt}} % dot denotes marking
\newcommand{\mbtu}{\mbt}% marked unlabeled binary tree
\newcommand{\mbtl}{\mbt^{\ell}}% marked labeled binary tree
\newcommand{\mbtun}{\mbtu_n}% marked unlabeled binary tree on n nodes
\newcommand{\mbtln}{\mbtl_n}% marked labeled binary tree on n nodes

\newcommand{\rmbt}{\dot{\rpbt}} % dot denotes marking
\newcommand{\rmbtu}{\rmbt}% marked unlabeled binary tree
\newcommand{\rmbtl}{\rmbt^{\ell}}% marked labeled binary tree
\newcommand{\rmbtun}{\rmbtu_n}% marked unlabeled binary tree on n nodes
\newcommand{\rmbtln}{\rmbtl_n}% marked labeled binary tree on n nodes


\newcommand{\dott}{\dot{T}} % a generic marked tree
%\newcommand{\spine}{\mathrm{spine}} % spine of tree
%\newcommand{\rec}{\mathrm{rec}}% records of a tree
%\newcommand{\internal}{\mathrm{int}}%internal node of a tree

\newcommand{\berntree}{\mathcal{T}^{B}} % Bernardi trees

\newcommand{\leftt}{\ell(T)} %number of left edges in T
\newcommand{\rightt}{\mathrm{r}(T)} % number of right edges in T

%%%%%%%%%%%%%%%%%%% hyper  arrangements
\newcommand{\hypcat}{\mathcal{C}} % Catalan
\newcommand{\hyplin}{\mathcal{L}} % Linial
\newcommand{\hypbra}{\mathcal{B}} % Braid
\newcommand{\hypshi}{\mathcal{S}} % Shi

%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%% alphabet
\newcommand{\alpu}{\mathsf{u}}
\newcommand{\alpv}{\mathsf{v}}
\newcommand{\alpm}{\mathsf{m}}
\newcommand{\alpx}{\mathsf{x}} % commutative alphabet
\newcommand{\alpX}{\mathsf{X}} % noncommutative alphabet
\newcommand{\rasc}{\mathrm{rasc}}
\newcommand{\lasce}{\mathrm{lasc}}
\newcommand{\rdes}{\mathrm{rdes}}
\newcommand{\ldes}{\mathrm{ldes}}
\newcommand{\nsym}{\mathbf{NSym}}% noncommutative symmetric functions
\newcommand{\nc}[1]{\mathbf{#1}} % make bold face noncommutative analog
\newcommand{\fir}[1]{\mathrm{first}(#1)} % first letter of a word
\newcommand{\las}[1]{\mathrm{last}(#1)}  % last letter of a word
\newcommand{\pre}[1]{\mathrm{pre}(#1)} % preorder traversal
\newcommand{\inor}[1]{\mathrm{in}(#1)} % inorder traversal
\newcommand{\fact}[1]{\mathrm{fact}(#1)} % factorizations set
\newcommand{\wt}[1]{\mathrm{wt}(#1)} % weight
\newcommand{\wtp}[1]{\mathrm{wt'}(#1)} %primed weight
\newcommand{\ssyt}[1]{\mathrm{SSYT}(#1)} % ssyt
\newcommand{\syt}[1]{\mathrm{SYT}(#1)} % syt
\newcommand{\rw}[1]{\mathrm{rw}(#1)} % reading word tableau


\newcommand{\term}[1]{\mathrm{Term}(#1)} % terminal nodes
\newcommand{\internal}[1]{\mathrm{Int}(#1)} % internal nodes
\newcommand{\biv}[1]{\mathrm{Bi}(#1)} % bivalent nodes
\newcommand{\univ}[1]{\mathrm{Uni}(#1)} % univalent nodes

\newcommand{\bivm}[1]{\mathrm{Bi}^{m}(#1)} % marked bivalent nodes
\newcommand{\bivu}[1]{\mathrm{Bi}^{u}(#1)} % unmarked bivalent nodes
\newcommand{\univrm}[1]{\mathrm{Uni}^{rm}(#1)} % marked right uninodes
\newcommand{\univlm}[1]{\mathrm{Uni}^{lm}(#1)} % marked left uninodes
\newcommand{\univm}[1]{\mathrm{Uni}^{m}(#1)} % marked uninodes
\newcommand{\univu}[1]{\mathrm{Uni}^{u}(#1)} % unmarked uninodes
\newcommand{\typ}[1]{\mathbf{c}(#1)} % type of a tree
\newcommand{\ltyp}[1]{\widecheck{\mathbf{c}}(#1)} % upper type of a marked tree
\newcommand{\utyp}[1]{\widehat{\mathbf{c}}(#1)} % lower type of a marked tree

\newcommand{\al}{\alpha}
\newcommand{\shape}[1]{\mathrm{sh}(#1)} %underlying shape of a tree
\newcommand{\can}[1]{\mathrm{Can}(#1)} %canopy of a tree



%Stuff added for this paper-Sean
\newcommand{\canopy}{v}
\newcommand{\pgseq}{u}
\newcommand{\nodered}{red!55}
\newcommand{\nodegreen}{green!40}
\newcommand{\tail}{\tau}
\newcommand{\push}{\mathcal{P}}
\newcommand{\glide}{\mathcal{G}}
\newcommand{\infw}{W}
\newcommand{\subword}{w}
\newcommand{\wti}{\mathrm{wt}_i}
\newcommand{\alps}{\mathsf{s}} % noncommutative s variable
\newcommand{\alpt}{\mathsf{t}} % noncommutative t variable
\renewcommand{\bP}{\mathbb{P}} % commandeering your macros lol
\DeclareMathOperator{\inorder}{in} % inorder word
\DeclareMathOperator{\std}{std} % standardization of a word (note: also defined above as stan)
\DeclareMathOperator{\rt}{root} % root of a tree
\usepackage{enumerate}
\usepackage{tabu}
\newcommand{\biva}[1]{\mathrm{Bi^a}(#1)} % bivalent nodes whose right edge is a weak ascent
\newcommand{\bivd}[1]{\mathrm{Bi^d}(#1)} % bivalent nodes whose right edge is a strict descent
%Note: Uni^a and Uni^d are only used in Fixed Canopy subsection for right-leaning trees
\newcommand{\univaU}[1]{\mathrm{Uni^a_U}(#1)} % univalent nodes whose edge is a weak ascent, marked with a U
\newcommand{\univaD}[1]{\mathrm{Uni^a_D}(#1)} % univalent nodes whose edge is a weak ascent, marked with a D
\newcommand{\univdU}[1]{\mathrm{Uni^d_U}(#1)} % univalent nodes whose edge is a strict descent, marked with a U
\newcommand{\univdD}[1]{\mathrm{Uni^d_D}(#1)} % univalent nodes whose edge is a strict descent, marked with a D

%\usepackage[ruled]{algorithm2e}
\usetikzlibrary{shapes.geometric} % for subtree triangles
\usetikzlibrary{backgrounds}
\usepackage{enumitem}
\setlist{nolistsep}


\title[Schur positivity and labeled binary trees]{Schur positivity and labeled binary trees}

\author{Ira M. Gessel\addressmark{1}, Sean Griffin\thanks{\href{mailto:stgriff@uw.edu}{stgriff@uw.edu}. Partially supported by the Achievement Rewards for College Scientists Foundation and N.S.F.\ Grant 1101017.}\addressmark{2} \and Vasu Tewari\thanks{Supported by an A.M.S.\ Simons travel grant.}\addressmark{2}}

\address{\addressmark{1}Department of Mathematics, Brandeis University, Waltham, MA 02453\\ \addressmark{2}Department of Mathematics, University of Washington, Seattle, WA 98195}

\received{\today}

\iffalse
\abstract{
The first author introduced a multivariate generating function that tracks the distribution of ascents and descents on labeled plane binary trees. 
In addition to proving that it is symmetric, he conjectured that it was Schur positive. 
In this article, we give two proofs of this conjecture. 
Central to our approach in the first proof is a weighted extension of a bijection of Pr\'eville-Ratelle and Viennot relating pairs of paths and    binary trees. 
In fact, this proof allows us to establish a stronger version of this conjecture showing the generating function restricted to labeled    binary trees with a fixed canopy is still Schur positive.
Our second proof takes Gessel's functional equation as the starting point, and studies a lift thereof in the setting of noncommutative symmetric functions.
We then solve this noncommutative functional equation and show that the solution expands positively in the basis of noncommutative ribbon Schur functions.
Finally, we apply our results to construct a $\mathfrak{S}_n$ action on a set of trees defined by Bernardi and shown to be equinumerous to the number of regions in the Linial arrangement. 
We further go on to show the $\gamma$-positivity for the distribution of right descents over local binary search trees.
}
\fi
\abstract{
The first author introduced a multivariate generating function that tracks the distribution of ascents and descents on labeled plane binary trees and conjectured that it was Schur positive. 
In this article, we give a sketch for a proof of the stronger statement that the generating function restricted to trees with a fixed canopy is Schur positive.
Central to our approach is a weighted extension of a bijection of Pr\'eville-Ratelle and Viennot relating pairs of paths and binary trees. 
We apply our results to construct a $\mathfrak{S}_n$-action on the regions of the Linial arrangement using a bijection of Bernardi. 
We then establish the $\gamma$-positivity for the distribution of right descents over local binary search trees.
}

\keywords{canopy, labeled trees, Schur positivity,  gamma-positivity}


\begin{document}
\maketitle

\section{Introduction}
The study of permutation statistics is a classical theme in algebraic combinatorics. One statistic which has shown up in surprisingly many areas of mathematics is the descent statistic.
In this article, we study a natural analogue of the descent statistic in the setting of labeled plane binary trees. 
Our results demonstrate that much more remains to be done in this regard, hints of which we provide in \cref{sec: back to the future}.

Given a positive integer $n$, let $\pbtln$ ($\pbtun$) denote the set of labeled (respectively unlabelled) plane binary trees on $n$ nodes. 
The labels on the nodes are drawn from the set of positive integers $\bP$, allowing repeated labels.
All trees referred to in this extended abstract will be plane binary trees, where we distinguish left children from right children.
The ascent and descent statistics on labeled trees come in two flavors each, depending on whether one compares the label of the parent node to the label of its right child or the label of its left child.
The first author, in the 1990s, initiated their study, and established a functional equation for the generating function keeping track of these statistics over the set of standard labeled trees. 
A \emph{standard labeled tree} $T\in \pbtln$ is a labeled tree with distinct labels drawn from $[n]:=\{1,\ldots,n\}$.
Given a labeled tree $T$, let the \emph{weight} of $T$ be
\begin{equation}\label{eqn:treewt}
  \wt{T} = a_1^{\rasc(T)}a_2^{\rdes(T)}b_1^{\lasce(T)}b_2^{\ldes(T)},
\end{equation}
where $\lasce$, $\ldes$, $\rasc$ and $\rdes$ record the number of ascents and descents in the labeling to the left and right, such that $\rasc$ and $\ldes$ are given by weak inequalities, while $\rdes$ and $\lasce$ are given by strict inequalities.
For example, a node labeled $2$ with a right child labeled $4$ is considered a right ascent in the labeling.
We will say that the edge between these two nodes has weight $a_1$.
This given, consider the following generating function
\begin{equation}
B:=B(x)=
\sum_{n\geq 1}
\sum_{\text{standard } T\in \pbtln}\wt{T} \frac{x^n}{n!}.
 \end{equation}

In unpublished work, the first author established that $B$ satisfies an elegant functional equation that sheds light on the symmetries present in $B$ and generalizes the well-known formula for the exponential generating function whose coefficients are the Eulerian polynomials.
Subsequently, proofs of this functional equation were also given by Kalikow \cite{Kalikow} and Drake \cite{Drake}. Recent work involving the generating function $B$ was inspired by the first author's observation that certain evaluations of $B$ coincided with the number of regions in well-known deformations of Coxeter arrangements. This viewpoint has been pursued in \cite{Corteel-Forge-Ventos, Forge, Tewari}, and a complete explanation has been offered by Bernardi \cite{Bernardi}.

 

Our primary object of study is a multivariate generalization of $B$.
To this end, let $\alpx =\{x_1,x_2,\ldots\}$ be a commuting set of indeterminates.
To every $T\in \pbt_n^{\ell}$, we associate a monomial $\alpx_T$ as follows: For a vertex $v\in T$ labeled $i$, let $x_v:=x_i$, and let $\alpx_T=\prod_{v\in T}x_v$.
Consider the following power series in $\alpx$ with coefficients in the semiring $\bN[a_1,a_2,b_1,b_2]$ of polynomials on $\{a_1,a_2,b_1,b_2\}$ with nonnegative integer coefficients.
\begin{equation}
S:=S(\alpx)=\sum_{n\geq 1}\sum_{T\in \pbtln}\wt{T}\alpx_T.
\end{equation}

For $n\geq 1$, let $G_n:=G_n(\alpx)$ denote the degree $n$ homogeneous summand of $S$ only summing over labeled trees on $n$ nodes. Clearly, $S=\sum_{n\geq 1}G_n$.
The first author established a functional equation that revealed that $S$ is a symmetric function in the $x_i$ variables and then made the following conjecture based on empirical evidence.

\begin{conjecture}\label{conj: schur positivity}
$S$ is Schur positive, meaning that $S$ may be expressed as a sum of Schur functions $s_\lambda$ with coefficients in $\bN[a_1,a_2,b_1,b_2]$.
\end{conjecture}
This conjecture served as the primary motivation for the line of research outlined in this extended abstract. In fact, we show a stronger fact; that $S$ may be expressed as a sum of Schur functions with coefficients in $\bN[a_1b_2,a_2b_1,a_1+b_2,a_2+b_1]$. 
This theorem follows from a recursive formula satisfied by $S$, which is~\eqref{eqn:ribbon functional equation} below.
In this extended abstract, we introduce the algorithm \texttt{ExtendedPG}, which is a weighted extension of the Pr\'eville-Ratelle-Viennot bijection between certain pairs of paths and binary trees and describe how it can be used to decompose a labeled binary tree into subtrees in order to prove \cref{thm: ribbon functional equation}.
\begin{theorem}\label{thm: ribbon functional equation}
Let $r_\alpha$ denote the ribbon Schur function indexed by the composition $\alpha$ and let $\ell(\alpha)$ denote the length of $\alpha$. Then we have that
  \begin{equation}\label{eqn:ribbon functional equation}
    S = \sum_{n\geq 1}\sum_{\alpha\vDash n} (a_1b_2S+a_1+b_2)^{n-\ell(\alpha)}(a_2b_1S+a_2+b_1)^{\ell(\alpha)-1}\,r_\alpha.
  \end{equation}
\end{theorem}
The \emph{canopy} of a binary tree $T\in\pbtun$ is a certain word of length $n-1$ on the alphabet $\{U,D\}$.
See the end of \cref{sec: preliminaries} for its precise definition.
We can then consider the refinement of $S$ only summing over labeled trees with a fixed canopy $\canopy$,
\begin{equation}
G_{n,\canopy}:=G_{n,\canopy}(\alpx)=\sum_{T\in \pbt_{n,\canopy}^{\ell}}\wt{T}\alpx_T,
\end{equation}
where $\pbt_{n,\canopy}^{\ell}\subseteq \pbtln$ is the set of labeled trees with canopy $\canopy$. We will describe in \cref{sec: PG proof} how $\texttt{ExtendedPG}$ also provides a proof that each $G_{n,\canopy}$ is Schur positive, which is a refinement of \cref{thm: ribbon functional equation}.
\begin{theorem}\label{thm: refined Schur positivity}
Fix $n\in \bP$, and let $\canopy$ be a word of length $n-1$ in the alphabet $\{U,D\}$. Then $G_{n,\canopy}$ is Schur positive.
\end{theorem}
Our proof also yields an explicit Schur positive expansion of $G_{n,\canopy}$ and consequently yields a Schur positive expansion of $G_n$.
We state the expansion of $G_n$ in \cref{cor: expansion using marked trees} but omit its proof.
We also omit the expansion of $G_{n,\canopy}$.

First, let us call a binary tree \emph{right-leaning} if every node which has a left child also has a right child.
Let the set of right-leaning binary trees on $n$ nodes be denoted by $\rpbt_n$.
Furthermore, let $\rmbtun$ denote the set of right-leaning trees on $n$ nodes with some subset of internal nodes marked.
As a Corollary to \cref{thm: ribbon functional equation}, we have the following explicit expansion for $G_n$ in terms of right-leaning trees.
\begin{corollary}\label{cor: expansion using marked trees}
  Let $\bivu{\dott}$ ($\bivm{\dott}$) denote the number of unmarked (respectively marked) internal nodes with two children, and let $\univu{\dott}$ ($\univm{\dott}$) denote the number of unmarked (respectively marked) internal nodes with only one child (which has to be a right child given the definition of $\rmbtun$). Then $G_n$ has the expansion given in~\eqref{eqn:G_n Expansion}.
\end{corollary}
\begin{equation}\label{eqn:G_n Expansion}
G_n=\sum_{\dott\in \rmbtun}(a_1b_2)^{\bivu{\dott}}(a_2b_1)^{\bivm{\dott}}(a_1+b_2)^{\univu{\dott}}(a_2+b_1)^{\univm{\dott}}\sum_{\ltyp{\dott}\preccurlyeq \delta \preccurlyeq \utyp{\dott}}r_{\delta},
\end{equation}
where $\ltyp{\dott}$ and $\utyp{\dott}$ are certain compositions of $n$ associated to a marked  tree whose definitions we omit from this extended abstract, and $\preccurlyeq$ stands for the usual refinement order on compositions. A fact worth noting about~\eqref{eqn:G_n Expansion} is that the coefficient of $r_{\alpha}$ for every $\alpha\vDash n$ belongs to $\bN[a_1b_2,a_2b_1,a_1+b_2,a_2+b_1]$ and furthermore, evaluates to the \emph{Catalan number} $\frac{1}{n+1}\binom{2n}{n}$ when we set $a_1=a_2=b_1=b_2=1$.  In particular, the coefficients of both $r_{(1,1,\dots,1)}$ and $r_{(n)}$ in~\eqref{eqn:G_n Expansion} are the \emph{homogenized Narayana polynomials}. Finally, the cardinalities of the sets $\rmbtun$ are the \emph{large Schr\"oder numbers}.

We conclude the introduction with an outline of the article. 
In \cref{sec: preliminaries}, we introduce our main combinatorial objects and develop all the notation we need.
In \cref{sec: PG proof}, we state the algorithm \texttt{ExtendedPG} and describe how it can be used to prove \cref{thm: ribbon functional equation,thm: refined Schur positivity}.
In \cref{sec: lbs}, we discuss some consequences of our results with a special emphasis on local binary search trees. Finally, we conclude with further avenues in \cref{sec: back to the future}.

\section{Combinatorial preliminaries}\label{sec: preliminaries}
In  this section, we will introduce the main combinatorial objects of this article.
Let $\bP$ be the set of positive integers. Let $\bP^+$ be the set of nonempty words on $\bP$.
Let $w = w_1w_2\dots w_n\in \bP^+$ be a nonempty word.
An \emph{inversion} of $w$ is a pair $(i,j)$ with $1\leq i<j\leq n$ such that $w_i>w_j$.
The set of inversions of $w$ is its \emph{inversion set}.
Let the \emph{standardization} of $w$ be the unique permutation $\std(w)\in\mathfrak{S}_n$ whose inversion set is the same as that of $w$.
To the word $w$, we associate the monomial $\alpx_w = x_{w_1}x_{w_2}\dots x_{w_n}$.

For notions related to the algebra of symmetric functions, denoted by $\Sym$, that are not made explicit here, we refer the reader to \cite{Stanley-EC2}.
An important class of symmetric functions for us is that of \emph{ribbon Schur functions}, which are indexed by compositions. To each composition $\alpha = (\alpha_1,\alpha_2,\dots,\alpha_k)$ of $n$, we associate a subset of $[n-1]$ defined by $\set(\alpha) := \{\alpha_1,\alpha_1+\alpha_2,\dots,\alpha_1+\dots+\alpha_{k-1}\}\subset[n-1]$. The ribbon Schur function associated to $\alpha$ is defined as
\begin{equation}
  r_\alpha := r_\alpha(\alpx) = \sum x_{i_1}x_{i_2}\dots x_{i_n},
  \end{equation}
  where the sum is over all $n$-tuples $(i_1,i_2,\dots,i_n)$ of positive integers satisfying $i_j > i_{j+1}$ if and only if $j\in \set(\alpha)$ for $1\leq j\leq n-1$.
  
  Note that the nodes of a binary tree can be categorized into \emph{leaf nodes}, which are nodes with no children, and \emph{internal nodes}, which are nodes with at least one child. 
We can classify the internal nodes further. We refer to an internal node with two children as a \emph{bivalent node}, and a node with only one child as a \emph{univalent node}.
Given a binary tree $T$, the sets of univalent nodes and bivalent nodes will be denoted by $\biv{T}$ and $\univ{T}$ respectively.


We will work with two different types of orderings on the nodes of a binary tree $T$ derived from a traversal of its nodes.
The \emph{preorder traversal} is defined recursively, where we first record the root, then traverse the right subtree of $T$ in preorder, and finally the left subtree of $T$ in preorder. 
The \emph{inorder traversal} is defined similarly, where we first traverse the left subtree of $T$ recursively in inorder, then record the root of $T$, and finally traverse the right subtree of $T$ in inorder. 
Given a node $u$ in a labeled tree $T$, we refer to the label on $u$ as $u^{\ell}$.
The preorder and inorder traversals naturally associate a reading word with a labeled tree, denoted $\pre{T}$ and $\inorder(T)$, respectively. 
Breaking $\pre{T}$ at the leaf nodes allows us to naturally associate a composition $\typ{T}$ to $T$.

To a plane binary tree $T\in \pbtun$ we can associate a word of length $n-1$ on the alphabet $\{U,D\}$ via the following process.
Traverse the tree with inorder traversal.
For each node traversed, record a $D$ if it is missing a left child, and then record a $U$ if it is missing a right child.
We obtain a word of length $n+1$ on the alphabet $\{U,D\}$ whose first letter is $D$ and last letter is $U$, and hence we may omit these letters.
The resulting word of length $n-1$ is called the \emph{canopy} of the tree, and will be denoted by $\can{T}$.


\section{A weighted extension of the Push-Gliding algorithm}\label{sec: PG proof}
In this section, we provide a sketch of a proof of \cref{thm: ribbon functional equation} using a weighted variant of the Push-Gliding algorithm of Pr\'eville-Ratelle and Viennot \cite{Preville-Ratelle-Viennot}.
The main result in \cite{Preville-Ratelle-Viennot} is a  generalization of the $m$-Tamari lattices to posets of arbitrary paths. 
Pr\'eville-Ratelle and Viennot were motivated by a question arising from what has come to be known as `rational Catalan combinatorics'. 

We will define a \emph{path} to be a sequence of nodes situated in the plane joined by up steps $U=(1,1)$ and down steps $D=(1,-1)$.
Let $(\pgseq,\canopy)$ be a pair of paths in the plane starting at $(0,0)$.
We shall call such a pair \emph{glued} if $\pgseq$ and $\canopy$ end at the same point and $\pgseq$ stays weakly above $\canopy$.
An equivalent variation of the Push-Gliding algorithm in \cite{Preville-Ratelle-Viennot} takes as input a glued pair of paths $(\pgseq,\canopy)$ and outputs a unique binary tree $T(\pgseq,\canopy)$.
We extend the algorithm to labeled paths and trees, keeping track of edge weights.

First let us establish some terminology used in our algorithms. Given a plane binary tree $T$ and a node $y$ in $T$, let $T_y$ be the subtree of $T$ rooted at $y$.
The \emph{right branch} of $T$ is the sequence of nodes in $T$ starting at the root and going right.
A \emph{tail} $\tail$ attached to the tree $T$ is a path whose first node is on the right branch of $T$ and whose first step is a $U$.
Let $\tail_i$ denote the $i^{th}$ node of $\tail$.
A \emph{labeled tail} of $T$ is a tail attached to the tree $T$ whose nodes are labeled with positive integers.
In our extended algorithm, at every step we keep track of a labeled binary tree $T$ and a labeled tail $\tail$ attached to $T$.
The weight associated to an edge, whether it is part of a tree or part of the tail, is indicated in \cref{fig:weightdiagram} based on the orientation of the edge, and the weight of a labeled tree or tail is the product of its edge weights.
\begin{figure}
\centering
  \scalebox{0.8}{
    \begin{tikzpicture}
      \tikzstyle{redcirc} = [circle,fill=\nodered,minimum size=12pt]
      \node[redcirc] (X) at (0,0){};
      \node[redcirc] (Y) at (1,-1){};
      \node at (Y) {$y$};
      \node at (X) {$x$};
      \draw (X)--(Y) node[midway,sloped,anchor=south,auto=false]{$\leq$}node[midway,below left=.1,inner sep=0]{$a_1$};
      % 
      \node[redcirc] (X'') at (2,0){};
      \node[redcirc] (Y'') at (3,-1){};
      \node at (X'') {$x$};
      \node at (Y'') {$y$};
      \draw (X'')--(Y'') node[midway,sloped,anchor=south,auto=false]{$>$}node[midway,below left=.1,inner sep=0]{$a_2$};
      % 
      \node[redcirc] (X') at (4,-1){};
      \node[redcirc] (Y') at (5,0){};
      \node at (Y') {$y$};
      \node at (X') {$x$};
      \draw (X')--(Y') node[midway,sloped,anchor=south,auto=false]{$\leq$}node[midway,below right=.1,inner sep=0]{$b_2$};
      % 
      \node[redcirc] (X''') at (6,-1){};
      \node[redcirc] (Y''') at (7,0){};
      \node at (X''') {$x$};
      \node at (Y''') {$y$};
      \draw (X''')--(Y''') node[midway,sloped,anchor=south,auto=false]{$>$}node[midway,below right=.1,inner sep=0]{$b_1$};
    \end{tikzpicture}
  }
  \caption{Determining the weight of a labeled edge.}
  \label{fig:weightdiagram}
\end{figure}

We first introduce the operations \texttt{WGlide} and \texttt{WPush}, illustrated in \cref{fig:glide,fig:push}, and then state our main algorithm \texttt{ExtendedPG}.
Each Glide and Push operations may change the weight $\wt{T,\tail} := \wt{T}\wt{\tail}$, but these changes will only involve the nodes $x$, $y$ and $z$ indicated in \cref{fig:glide,fig:push}.
It can be checked that before and after these operations, the weights of the two bold edges only depend on the standardization of the word read from their labels, $\std(x^\ell y^\ell z^\ell)$. Furthermore, all other edge weights are preserved.
The following claim allow us to track $\wt{T,\tail}$.
\begin{claim}
  In Cases $(\push 1)$ and $(\glide 1)$ of \cref{alg:WGlide,alg:WPush}, $\wt{T,\tail}=\wt{T',\tail'}$. In Cases $(\push 2)$ and $(\glide 2)$, the combined weight of the edges $xz$ and $yz$ in $T'$ is $a_1b_2$ if $x^\ell\leq z^\ell$ or $a_2b_1$ if $x^\ell>z^\ell$.
\end{claim}

\begin{algorithm}[h]
  \caption{\texttt{WGlide}\label{alg:WGlide}}
  \KwIn{$(T,\tail,I)$: $T\in\pbtl$, $\tail$ a tail attached to $T$, $I$ a set of nodes in $T$.}
  \tcp*[f]{Assume $\tail_1\neq\rt(T)$.}

  \KwOut{$(T',\tail',I')$: $T'\in\pbtl$, $\tail'$ a tail attached to $T'$, $I'$ a set of nodes in $T'$.}
  \Begin{
    Let $y:= \tail_1$, and let $z:= \tail_2$\;
    Let $x$ be the parent of $y$ in $T$\;
    Let $\tail'$ be obtained from $\tail$ by replacing the starting node $y$ with $x$\;
    \lIf{$\std(x^\ell y^\ell z^\ell)\in \{123,213,231\}$}{
      \KwRet{$(T,\tail',I)$}\tcp*[f]{Case $(\glide 1)$}
    }
    \lElse{
      \KwRet{$(T,\tail',I\cup T_y)$}\tcp*[f]{Case $(\glide 2)$}
    }
    }
\end{algorithm}

\begin{algorithm}[H]
  \caption{\texttt{WPush}\label{alg:WPush}}
  \KwIn{$(T,\tail,I)$: $T\in\pbtl$, $\tail$ a labeled tail attached to $T$, $I$ a set of nodes in $T$.}
  \KwOut{$(T',\tail',I')$: $T'\in\pbtl$, $\tail'$ a labeled tail attached to $T'$, $I'$ a set of nodes in $T'$.}
  \Begin{
    Let $y:= \tail_1$, and let $z:= \tail_2$\;
    Let $(z,\tail_3,\tail_4,\dots,\tail_k)$ is the longest segment of $\tail$ starting at $z$ going down, let $\rho = (\tail_3,\tail_4,\dots,\tail_k)$, considered as a (possibly empty) tree with only right children\;
    Let $T''$ be the tree with root $z$, left subtree $T_y$ and right subtree $\rho$\;
    Let $T'$ be the tree obtained from $T$ by replacing $T_y$ with $T''$\;
    Let $\tail'$ be the final segment of $\tail$ starting at $\tail_k$\;
    \uIf{$y$ has a parent $x$ in $T$}{
      \lIf{$\std(x^\ell y^\ell z^\ell)\in \{132,312,321\}$}{
        \KwRet{$(T',\tail',I)$}\tcp*[f]{Case $(\push 1)$}
      }
      \lElse{
        \KwRet{$(T',\tail',I\cup T_y)$}\tcp*[f]{Case $(\push 2)$}
      }
  }
  \Else{\KwRet{$(T',\tail',I)$}}
   }
 \end{algorithm} 

\begin{figure}[H]
  \newcommand{\tempfontsize}{\LARGE}
  \centering
  \begin{minipage}[b]{0.45\textwidth}
    \centering
    \scalebox{0.45}{
      \begin{tikzpicture}[scale=0.85]
        \tikzstyle{every node} = [font=\LARGE]
        \tikzstyle{pathnode} = [circle,draw,minimum size = 0.7cm]
        \tikzstyle{glide} = [thick,red]
        \tikzstyle{push} = [thick,blue]
        \tikzstyle{rednode} = [circle,fill=\nodered,minimum size=0.7cm]
        \tikzstyle{tri}=[draw,isosceles triangle,shape border rotate=90,minimum size=0.7cm,inner sep=0,below,fill=\nodered,\nodered]
        \tikzstyle{boldedge} = [line width=1mm];
        % tree
        \node[rednode] (v1) at (0,0){};
        \node[rednode] (v2) at (1,-1){};
        \node[rednode] (v3) at (2,-2){};
        \coordinate (v1') at (-1,-1);
        \coordinate (v2') at (0,-2);
        \coordinate (v3') at (1,-3);
        \coordinate (v4) at (3,-3){};
        \node[tri] at (v1'){};
        \node[tri] at (v2'){};
        \node[tri] at (v3'){};
        \node[tri] at (v4){};
        \draw (v1)--(v2);
        \draw[boldedge] (v2)--(v3);
        \draw (v3)--(v4);
        \draw (v1)--(v1');
        \draw (v2)--(v2');
        \draw (v3)--(v3');
        % path
        \node[pathnode] (p1) at (3,-1){};
        \node[pathnode] (p2) at (4,-2){};
        \node[pathnode] (p3) at (5,-3){};
        \node[pathnode] (p4) at (6,-2){};
        \draw[boldedge] (v3)--(p1);
        \draw (p1)--(p2);
        \draw[dashed] (p2) edge (p3);
        \draw (p3)--(p4);
        % labels
        \node at (v2){$x$};
        \node at (v3){$y$};
        \node at (p1){$z$};
        % Arrow
        \draw[->] (7,-2) -- (8,-2) node[midway,above]{\LARGE $\glide$};
        % 
        \begin{scope}[xshift = 10cm]
          % tree
          \node[rednode] (v1) at (0,0){};
          \node[rednode] (v2) at (1,-1){};
          \node[rednode] (v3) at (2,-2){};
          \coordinate (v1') at (-1,-1);
          \coordinate (v2') at (0,-2);
          \coordinate (v3') at (1,-3);
          \coordinate (v4) at (3,-3){};
          \node[tri] at (v1'){};
          \node[tri] at (v2'){};
          \node[tri] at (v3'){};
          \node[tri] at (v4){};
          \draw (v1)--(v2);
          \draw[boldedge](v2)--(v3);
          \draw (v3)--(v4);
          \draw (v1)--(v1');
          \draw (v2)--(v2');
          \draw (v3)--(v3');
          % path
          \node[pathnode] (p1) at (2,0){};
          \node[pathnode] (p2) at (3,-1){};
          \node[pathnode] (p3) at (4,-2){};
          \node[pathnode] (p4) at (5,-1){};
          \draw[boldedge] (v2)--(p1);
          \draw (p1)--(p2);
          \draw[dashed] (p2) edge (p3);
          \draw (p3)--(p4);
          % labels
          \node at (v2){$x$};
          \node at (v3){$y$};
          \node at (p1){$z$};
          \node at (0,-4.7){};%For symmetry
        \end{scope}
      \end{tikzpicture}
    }
    \caption{Glide Operation}
    \label{fig:glide}
  \end{minipage}
  \begin{minipage}[b]{0.45\textwidth}
    \centering
    \scalebox{0.45}{
      \begin{tikzpicture}[scale=0.85]
        \tikzstyle{every node} = [font=\LARGE]
        \tikzstyle{pathnode} = [circle,draw,minimum size = 0.7cm]
        \tikzstyle{glide} = [thick,red]
        \tikzstyle{push} = [thick,blue]
        \tikzstyle{rednode} = [circle,fill=\nodered,minimum size=0.7cm]
        \tikzstyle{tri}=[draw,isosceles triangle,shape border rotate=90,minimum size=0.7cm,inner sep=0,below,fill=\nodered,\nodered]
        \tikzstyle{boldedge} = [line width=1mm];
        % tree
        \node[rednode] (v1) at (0,0){};
        \node[rednode] (v2) at (1,-1){};
        \node[rednode] (v3) at (2,-2){};
        \coordinate (v1') at (-1,-1);
        \coordinate (v2') at (0,-2);
        \coordinate (v3') at (1,-3);
        \coordinate (v4) at (3,-3){};
        \node[tri] at (v1'){};
        \node[tri] at (v2'){};
        \node[tri] at (v3'){};
        \node[tri] at (v4){};
        \draw (v1)--(v2);
        \draw[boldedge] (v2)--(v3);
        \draw (v3)--(v4);
        \draw (v1)--(v1');
        \draw (v2)--(v2');
        \draw (v3)--(v3');
        % path
        \node[pathnode] (p1) at (3,-1){};
        \node[pathnode] (p2) at (4,-2){};
        \node[pathnode] (p3) at (5,-3){};
        \node[pathnode] (p4) at (6,-2){};
        \draw[boldedge] (v3)--(p1);
        \draw (p1)--(p2);
        \draw[dashed] (p2) edge (p3);
        \draw (p3)--(p4);
        % labels
        \node at (v2){$x$};
        \node at (v3){$y$};
        \node at (p1){$z$};
        \draw[->] (7,-2) -- (8,-2) node[midway,above]{\LARGE $\push$};
        \begin{scope}[xshift = 10cm]
          % tree
          \node[rednode] (w1) at (0,0){};
          \node[rednode] (w2) at (1,-1){};
          \node[rednode] (w3) at (1,-3){};
          \coordinate (w1') at (-1,-1);
          \coordinate (w2') at (0,-2);
          \coordinate (w3') at (0,-4);
          \coordinate (w4) at (2,-4);
          \node[tri] at (w1'){};
          \node[tri] at (w2'){};
          \node[tri] at (w3'){};
          \node[tri] at (w4){};
          \draw (w1)--(w2);
          \draw (w3)--(w4);
          \draw (w1)--(w1');
          \draw (w2)--(w2');
          \draw (w3)--(w3');
          % path
          \node[rednode] (q1) at (2,-2){};
          \node[rednode] (q2) at (3,-3){};
          \node[rednode] (q3) at (4,-4){};
          \node[pathnode] (q4) at (5,-3){};
          \draw[boldedge] (w3)--(q1);
          \draw (q1)--(q2);
          \draw[dashed] (q2) edge (q3);
          \draw (q3)--(q4);
          \draw[boldedge] (w2)--(q1);
          % labels
          \node at (w2){$x$};
          \node at (w3){$y$};
          \node at (q1){$z$};
        \end{scope}
      \end{tikzpicture}
    }
    \caption{Push Operation}
    \label{fig:push}
  \end{minipage}
\end{figure}


\begin{algorithm}[h]
  \caption{\texttt{ExtendedPG}\label{alg:ExtendedPG}}
  \KwIn{$(\pgseq,\canopy)$: A glued pair of paths with a labeling of $\canopy$.}
  \KwOut{$(T(\pgseq,\canopy),I)$: $T(\pgseq,\canopy)\in \pbtl$, a set $I$ of ``infected'' nodes of $T(\pgseq,\canopy)$.}
  \SetKwFunction{WPush}{WPush}
  \SetKwFunction{WGlide}{WGlide}
    \Begin{
      \If{$\canopy$ consists of only down steps}{
        \KwRet{$(\canopy,\emptyset)$}\tcp*[f]{Consider $\canopy$ a tree with only right children}\;
      }
      Translate $\pgseq$ into a word $\pgseq'$ on the alphabet $\{\push,\glide\}$ by replacing each $U$ with a $\push$ and each $D$ with a $\glide$\;
      Let $T$ be the longest initial segment of $\canopy$ consisting of $D$ steps\;
      Let $\tail$ be the final segment of $\canopy$ starting at the rightmost child of $T$\;
      $I\longleftarrow\emptyset$\;
      \While{$\tail$ is not a single node}{
        \uIf{$\pgseq'_1 == \push$}{
          $(T,\tail,I) \longleftarrow \WPush(T,\tail,I)$\;
          Remove $\push$ from the front of $\pgseq'$\;
        }
        \Else{
          $(T,\tail,I)\longleftarrow \WGlide(T,\tail,I)$\;
          Remove $\glide$ from the front of $\pgseq'$\;
        }
      }
      \KwRet{$(T,I)$}
      }
    \end{algorithm}

Pr\'eville-Ratelle and Viennot have shown the original Push-Gliding algorithm involving unlabeled paths and trees is a bijection such that $\can{T(\pgseq,\canopy)} = \canopy$.
An example of \cref{alg:ExtendedPG} is demonstrated in \cref{fig: Weighted PG}.
Uninfected tree nodes are shaded dark red, infected tree nodes are shaded light green, and path nodes are circled.
Given an input $(\pgseq,\canopy)$ for \cref{alg:ExtendedPG}, let $W$ be the word read off from the labeling of $\canopy$ in order.
Note that $W = \inorder(T(\pgseq,\canopy))$.
If $I$ is the set of infected nodes which \cref{alg:ExtendedPG} returns, let $\subword = \subword_1\subword_2\dots\subword_\ell$ be the subword of $\infw$ of the labels of the nodes not in $I$. 
\begin{claim}
  The set $I$ is the disjoint union of the maximal infected subtrees of $T(\pgseq,\canopy)$. The inorder reading words of these trees form nonadjacent intervals in $\infw$.
\end{claim}

Assuming the above claim, then there exist subtrees $T_1$, $T_2$,\dots, $T_{m-1}$ of the final output tree $T$ such that for each $i$, $T_i$ is either empty or a maximally infected subtree of $T$, and such that $\infw~=~\subword_1\inorder(T_1)\subword_2\cdots\subword_{\ell-1}\inorder(T_{\ell-1})\subword_\ell$.


In the example in \cref{fig: Weighted PG}, $\subword~=~213455$, $T_1$ consists of a single node labeled $1$, $T_4$ is the green subtree consisting of three nodes labeled $342$ in inorder, and $T_2=T_3=T_5=\emptyset$.
For $i$ such that $T_i=\emptyset$, then $\subword_i$ and $\subword_{i+1}$ are adjacent nodes in $\canopy$.
If these nodes form an up step, let us denote this by $\subword_i\subword_{i+1}=U$ and similarly for a down step. Define
\[
  \wti = \begin{cases}
        a_1[\subword_i\subword_{i+1} = D]+b_2[\subword_i\subword_{i+1}=U] & \text{if $T_i=\emptyset$ and $\subword_i\leq \subword_{i+1}$},\\
        a_2[\subword_i\subword_{i+1}=D]+b_1[\subword_i\subword_{i+1}=U] & \text{if $T_i = \emptyset$ and $\subword_i>\subword_{i+1}$},\\
        a_1b_2 & \text{if $T_i\neq \emptyset$ and $\subword_i\leq \subword_{i+1}$},\\
        a_2b_1 & \text{if $T_i\neq \emptyset$ and $\subword_i>\subword_{i+1}$}.
      \end{cases}
  \]
  where if $P$ is a statement, $[P]$ evaluates to $1$ if true and $0$ if false.
  Therefore, the sequence of weights $\wti$ in our example is $(a_2b_1,a_1,b_2,a_1b_2,a_1)$. It can be seen that $x_\subword = x_2x_1x_3x_4x_5^2$ is a term in $r_{(1,5)}$, and the decomposition corresponds to a term in the expansion of $(a_2b_1S)(a_1)(b_2)(a_1b_2S)(a_1)r_{(1,5)}$, which is part of the sum in~\eqref{eqn:ribbon functional equation}.

Given a labeled binary tree $T$, it corresponds to a unique glued pair of paths $(\pgseq,\canopy)$ where $\canopy$ is labeled with the word $\inorder(T)$.
Performing \cref{alg:ExtendedPG} on this pair yields a decomposition of $T$, and the right-hand side of~\eqref{eqn:ribbon functional equation} can be interpreted in terms of these decompositions, as demonstrated in our example.
In fact, given a decomposition of a tree $T\in \pbtln$ into the subtrees $T_i$, the word $\subword$, and the weights $\wti$, the canopy $\can{T}$ can be recovered from this data.
If to each subtree $T_i=\emptyset$ we associate the $U$ or $D$ step given by $\wti$ and to each $T_i\neq \emptyset$ we associate $D\can{T_i}U$, then $\can{T}$ is the sequence of steps given by concatenating these sequences in order.
From these observations, it is possible to prove \cref{thm: refined Schur positivity}.

\begin{figure}[!ht]
  \centering
  \resizebox{0.6\linewidth}{!}{
    \begin{tikzpicture}
      \tikzstyle{pathnode} = [circle,draw,minimum size = 14pt]
      \tikzstyle{glide} = [thick,red]
      \tikzstyle{push} = [thick,blue]
      \tikzstyle{rednode} = [circle,fill=\nodered,minimum size=14pt]
      \node at (-2,-0.5) {\Large $(\pgseq,\canopy)=$};
      \node[pathnode] (v1) at (0,0){};
      \node[pathnode] (v2) at (1,-1){};
      \node[pathnode] (v3) at (2,0){};
      \node[pathnode] (v4) at (3,-1){};
      \node[pathnode] (v5) at (4,0){};
      \node[pathnode] (v6) at (5,-1){};
      \node[pathnode] (v7) at (6,-2){};
      \node[pathnode] (v8) at (7,-1){};
      \node[pathnode] (v9) at (8,0){};
      \node[pathnode] (v10) at (9,-1){};
      \node at (v1) {$2$};
      \node at (v2) {$1$};
      \node at (v3) {$1$};
      \node at (v4) {$3$};
      \node at (v5) {$4$};
      \node at (v6) {$3$};
      \node at (v7) {$4$};
      \node at (v8) {$2$};
      \node at (v9) {$5$};
      \node at (v10) {$5$};
      \draw (v1)--(v2)--(v3)--(v4)--(v5)--(v6)--(v7)--(v8)--(v9)--(v10);
      \draw[glide,transform canvas={xshift=1pt,yshift=1pt}] (v1) -- (v2) node[midway,above]{$\glide$};
      \draw[push,transform canvas={xshift=-1pt,yshift=1pt}] (v2) -- (v3) node[midway,above]{$\push$};
      \draw[glide,transform canvas={xshift=1pt,yshift=1pt}] (v3) -- (v4) node[midway,above]{$\glide$};
      \draw[push,transform canvas={xshift=-1pt,yshift=1pt}] (v4) -- (v5) node[midway,above]{$\push$};
      \draw[push] (v5) -- (5,1) node[midway,above]{$\push$};
      \draw[glide] (5,1) -- (6,0) node[midway,above]{$\glide$};
      \draw[push] (6,0) -- (7,1) node[midway,above]{$\push$};
      \draw[glide] (7,1) -- (v9) node[midway,above]{$\glide$};
      \draw[glide,transform canvas={xshift=1pt,yshift=1pt}] (v9) -- (v10) node[midway,above]{$\glide$};
    \end{tikzpicture}
  }

  \resizebox{\linewidth}{!}{
    % \setlength{\extrarowheight}{20pt}
    % \begin{tabular*}{0.95\textwidth}{@{\extracolsep{\fill} } m{0.5cm} cccc}
    \begin{tabular}{cccccccc}
      % (1,1)
      \begin{tikzpicture}[scale=0.6]
        \tikzstyle{every node} = [font=\large]
        \tikzstyle{pathnode} = [circle,draw,minimum size = 14pt]
        \tikzstyle{glide} = [thick,red]
        \tikzstyle{push} = [thick,blue]
        \tikzstyle{rednode} = [circle,fill=\nodered,minimum size=14pt]
        % tree
        \node[rednode] (v1) at (0,0){};
        \node[rednode] (v2) at (1,-1){};
        % path
        \node[pathnode] (v3) at (2,0){};
        \node[pathnode] (v4) at (3,-1){};
        \node[pathnode] (v5) at (4,0){};
        \node[pathnode] (v6) at (5,-1){};
        \node[pathnode] (v7) at (6,-2){};
        \node[pathnode] (v8) at (7,-1){};
        \node[pathnode] (v9) at (8,0){};
        \node[pathnode] (v10) at (9,-1){};
        % labels
        \node at (v1) {$2$};
        \node at (v2) {$1$};
        \node at (v3) {$1$};
        \node at (v4) {$3$};
        \node at (v5) {$4$};
        \node at (v6) {$3$};
        \node at (v7) {$4$};
        \node at (v8) {$2$};
        \node at (v9) {$5$};
        \node at (v10) {$5$};
        \draw (v1)--(v2)--(v3)--(v4)--(v5)--(v6)--(v7)--(v8)--(v9)--(v10);
        \node at (4.5,-3) {$u' = \underline{\glide}\push\glide\push\push\glide\push\glide\glide$};
      \end{tikzpicture}
      % (1,2)
      &
        \begin{tikzpicture}
          \draw[->] (0,1) -- (1,1) node[midway,above]{$\glide 2$};
          \node (0) at (0,0){};
        \end{tikzpicture}
      &
      % (1,3)
        \begin{tikzpicture}[scale=0.6]
          \tikzstyle{every node} = [font=\large]
          \tikzstyle{pathnode} = [circle,draw,minimum size = 14pt]
          \tikzstyle{glide} = [thick,red]
          \tikzstyle{push} = [thick,blue]
          \tikzstyle{rednode} = [circle,fill=\nodered,minimum size=14pt]
          \tikzstyle{greennode} = [circle,fill=\nodegreen,minimum size=14pt]
          % tree
          \node[rednode] (v1) at (0,0){};
          \node[greennode] (v2) at (1,-1){};
          % path
          \node[pathnode] (v3) at (1,1){};
          \node[pathnode] (v4) at (2,0){};
          \node[pathnode] (v5) at (3,1){};
          \node[pathnode] (v6) at (4,0){};
          \node[pathnode] (v7) at (5,-1){};
          \node[pathnode] (v8) at (6,0){};
          \node[pathnode] (v9) at (7,1){};
          \node[pathnode] (v10) at (8,0){};
          % labels
          \node at (v1) {$2$};
          \node at (v2) {$1$};
          \node at (v3) {$1$};
          \node at (v4) {$3$};
          \node at (v5) {$4$};
          \node at (v6) {$3$};
          \node at (v7) {$4$};
          \node at (v8) {$2$};
          \node at (v9) {$5$};
          \node at (v10) {$5$};
          % edges
          \draw (v1)--(v2);
          \draw (v1)--(v3)--(v4)--(v5)--(v6)--(v7)--(v8)--(v9)--(v10);
          \node at (4,-2) {$u' = \underline{\push}\glide\push\push\glide\push\glide\glide$};
        \end{tikzpicture}
        % 
      &
      % (1,4) 
        \begin{tikzpicture}
          \draw[->] (0,1) -- (1,1) node[midway,above]{$\push$};
          \node (0) at (0,0){};
        \end{tikzpicture}
        % 
      &
      % (1,5)
        \begin{tikzpicture}[scale=0.6]
          \tikzstyle{every node} = [font=\large]
          \tikzstyle{pathnode} = [circle,draw,minimum size = 14pt]
          \tikzstyle{glide} = [thick,red]
          \tikzstyle{push} = [thick,blue]
          \tikzstyle{rednode} = [circle,fill=\nodered,minimum size=14pt]
          \tikzstyle{greennode} = [circle,fill=\nodegreen,minimum size=14pt]
          % tree
          \node[rednode] (v1) at (0,0){};
          \node[greennode] (v2) at (1,-1){};
          \node[rednode] (v3) at (1,1){};
          \node[rednode] (v4) at (2,0){};
          % path
          \node[pathnode] (v5) at (3,1){};
          \node[pathnode] (v6) at (4,0){};
          \node[pathnode] (v7) at (5,-1){};
          \node[pathnode] (v8) at (6,0){};
          \node[pathnode] (v9) at (7,1){};
          \node[pathnode] (v10) at (8,0){};
          % labels
          \node at (v1) {$2$};
          \node at (v2) {$1$};
          \node at (v3) {$1$};
          \node at (v4) {$3$};
          \node at (v5) {$4$};
          \node at (v6) {$3$};
          \node at (v7) {$4$};
          \node at (v8) {$2$};
          \node at (v9) {$5$};
          \node at (v10) {$5$};
          % edges
          \draw (v1)--(v2);
          \draw (v1)--(v3)--(v4)--(v5)--(v6)--(v7)--(v8)--(v9)--(v10);
          \node at (4,-2) {$u' = \underline{\glide}\push\push\glide\push\glide\glide$};
        \end{tikzpicture}
        % 
      &
      % (1,6)
        \begin{tikzpicture}
          \draw[->] (0,1) -- (1,1) node[midway,above]{$\glide 1$};
          \node (0) at (0,0){};
        \end{tikzpicture}
      &
      % (1,7)
        \begin{tikzpicture}[scale=0.6]
          \tikzstyle{every node} = [font=\large]
          \tikzstyle{pathnode} = [circle,draw,minimum size = 14pt]
          \tikzstyle{glide} = [thick,red]
          \tikzstyle{push} = [thick,blue]
          \tikzstyle{rednode} = [circle,fill=\nodered,minimum size=14pt]
          \tikzstyle{greennode} = [circle,fill=\nodegreen,minimum size=14pt]
          % tree
          \node[rednode] (v1) at (0,0){};
          \node[greennode] (v2) at (1,-1){};
          \node[rednode] (v3) at (1,1){};
          \node[rednode] (v4) at (2,0){};
          % path
          \node[pathnode] (v5) at (2,2){};
          \node[pathnode] (v6) at (3,1){};
          \node[pathnode] (v7) at (4,0){};
          \node[pathnode] (v8) at (5,1){};
          \node[pathnode] (v9) at (6,2){};
          \node[pathnode] (v10) at (7,1){};
          % labels
          \node at (v1) {$2$};
          \node at (v2) {$1$};
          \node at (v3) {$1$};
          \node at (v4) {$3$};
          \node at (v5) {$4$};
          \node at (v6) {$3$};
          \node at (v7) {$4$};
          \node at (v8) {$2$};
          \node at (v9) {$5$};
          \node at (v10) {$5$};
          % edges
          \draw (v1)--(v2);
          \draw (v1)--(v3);
          \draw (v3)--(v4);
          \draw (v3)--(v5)--(v6)--(v7)--(v8)--(v9)--(v10);
          \node at (3.5,-2) {$u' = \underline{\push}\push\glide\push\glide\glide$};
        \end{tikzpicture}
        % 
      &
      % (1,8)
        \begin{tikzpicture}
          \draw[->] (0,1) -- (1,1) node[midway,above]{$\push$};
          \node (0) at (0,0){};
        \end{tikzpicture}
        % 
      \\
      % (2,1)
      \begin{tikzpicture}[scale=0.6]
        \tikzstyle{every node} = [font=\large]
        \tikzstyle{pathnode} = [circle,draw,minimum size = 14pt]
        \tikzstyle{glide} = [thick,red]
        \tikzstyle{push} = [thick,blue]
        \tikzstyle{rednode} = [circle,fill=\nodered,minimum size=14pt]
        \tikzstyle{greennode} = [circle,fill=\nodegreen,minimum size=14pt]
        % tree
        \node[rednode] (v1) at (0,0){};
        \node[greennode] (v2) at (1,-1){};
        \node[rednode] (v3) at (1,1){};
        \node[rednode] (v4) at (2,0){};
        \node[rednode] (v5) at (2,2){};
        \node[rednode] (v6) at (3,1){};
        \node[rednode] (v7) at (4,0){};
        % path
        \node[pathnode] (v8) at (5,1){};
        \node[pathnode] (v9) at (6,2){};
        \node[pathnode] (v10) at (7,1){};
        % labels
        \node at (v1) {$2$};
        \node at (v2) {$1$};
        \node at (v3) {$1$};
        \node at (v4) {$3$};
        \node at (v5) {$4$};
        \node at (v6) {$3$};
        \node at (v7) {$4$};
        \node at (v8) {$2$};
        \node at (v9) {$5$};
        \node at (v10) {$5$};
        % edges
        \draw (v1)--(v2);
        \draw (v1)--(v3);
        \draw (v3)--(v4);
        \draw (v3)--(v5)--(v6)--(v7)--(v8)--(v9)--(v10);
        \node at (3.5,-2) {$u' = \underline{\push}\glide\push\glide\glide$};
      \end{tikzpicture}
      % 
      &
      % (2,2)
        \begin{tikzpicture}
          \draw[->] (0,1) -- (1,1) node[midway,above]{$\push 2$};
          \node (0) at (0,0){};
        \end{tikzpicture}
        % 
      &
      % (2,3)
        \begin{tikzpicture}[scale=0.6]
          \tikzstyle{every node} = [font=\large]
          \tikzstyle{pathnode} = [circle,draw,minimum size = 14pt]
          \tikzstyle{glide} = [thick,red]
          \tikzstyle{push} = [thick,blue]
          \tikzstyle{rednode} = [circle,fill=\nodered,minimum size=14pt]
          \tikzstyle{greennode} = [circle,fill=\nodegreen,minimum size=14pt]
          % tree
          \node[rednode] (v1) at (0,0){};
          \node[greennode] (v2) at (1,-1){};
          \node[rednode] (v3) at (1,1){};
          \node[rednode] (v4) at (2,0){};
          \node[rednode] (v5) at (2,2){};
          \node[rednode] (v6) at (3,1){};
          \node[greennode] (v7) at (3,-1){};
          \node[rednode] (v8) at (4,0){};
          % path
          \node[pathnode] (v9) at (5,1){};
          \node[pathnode] (v10) at (6,0){};
          % labels
          \node at (v1) {$2$};
          \node at (v2) {$1$};
          \node at (v3) {$1$};
          \node at (v4) {$3$};
          \node at (v5) {$4$};
          \node at (v6) {$3$};
          \node at (v7) {$4$};
          \node at (v8) {$2$};
          \node at (v9) {$5$};
          \node at (v10) {$5$};
          % edges
          \draw (v1)--(v2);
          \draw (v1)--(v3);
          \draw (v3)--(v4);
          \draw (v7)--(v8);
          \draw (v3)--(v5)--(v6)--(v8)--(v9)--(v10);
          \node at (3,-2) {$u' = \underline{\glide}\push\glide\glide$};
        \end{tikzpicture}
        % 
      &
      % (2,4)
        \begin{tikzpicture}
          \draw[->] (0,1) -- (1,1) node[midway,above]{$\glide 1$};
          \node (0) at (0,0){};
        \end{tikzpicture}
      &
      % (2,5)
        \begin{tikzpicture}[scale=0.6]
          \tikzstyle{every node} = [font=\large]
          \tikzstyle{pathnode} = [circle,draw,minimum size = 14pt]
          \tikzstyle{glide} = [thick,red]
          \tikzstyle{push} = [thick,blue]
          \tikzstyle{rednode} = [circle,fill=\nodered,minimum size=14pt]
          \tikzstyle{greennode} = [circle,fill=\nodegreen,minimum size=14pt]
          % tree
          \node[rednode] (v1) at (0,0){};
          \node[greennode] (v2) at (1,-1){};
          \node[rednode] (v3) at (1,1){};
          \node[rednode] (v4) at (2,0){};
          \node[rednode] (v5) at (2,2){};
          \node[rednode] (v6) at (3,1){};
          \node[greennode] (v7) at (3,-1){};
          \node[rednode] (v8) at (4,0){};
          % path
          \node[pathnode] (v9) at (4,2){};
          \node[pathnode] (v10) at (5,1){};
          % labels
          \node at (v1) {$2$};
          \node at (v2) {$1$};
          \node at (v3) {$1$};
          \node at (v4) {$3$};
          \node at (v5) {$4$};
          \node at (v6) {$3$};
          \node at (v7) {$4$};
          \node at (v8) {$2$};
          \node at (v9) {$5$};
          \node at (v10) {$5$};
          % edges
          \draw (v1)--(v2);
          \draw (v1)--(v3);
          \draw (v3)--(v4);
          \draw (v7)--(v8);
          \draw (v6)--(v8);
          \draw (v3)--(v5)--(v6)--(v9)--(v10);
          \node at (2.5,-2) {$u' = \underline{\push}\glide\glide$};
        \end{tikzpicture}
        % 
      &
      % (2,6)
        \begin{tikzpicture}
          \draw[->] (0,1) -- (1,1) node[midway,above]{$\push 2$};
          \node (0) at (0,0){};
        \end{tikzpicture}
      &
      % (2,7)
        \begin{tikzpicture}[scale=0.6]
          \tikzstyle{every node} = [font=\large]
          \tikzstyle{pathnode} = [circle,draw,minimum size = 14pt]
          \tikzstyle{glide} = [thick,red]
          \tikzstyle{push} = [thick,blue]
          \tikzstyle{rednode} = [circle,fill=\nodered,minimum size=14pt]
          \tikzstyle{greennode} = [circle,fill=\nodegreen,minimum size=14pt]
          % tree
          \node[rednode] (v1) at (-0.5,-0.5){};
          \node[greennode] (v2) at (0.5,-1.5){};
          \node[rednode] (v3) at (0.5,0.5){};
          \node[rednode] (v4) at (1.5,-0.5){};
          \node[rednode] (v5) at (2,2){};
          \node[greennode] (v6) at (2.5,-0.5){};
          \node[greennode] (v7) at (2.5,-2.5){};
          \node[greennode] (v8) at (3.5,-1.5){};
          \node[rednode] (v9) at (3.5,0.5){};
          \node[rednode] (v10) at (4.5,-0.5){};
          % path
          % labels
          \node at (v1) {$2$};
          \node at (v2) {$1$};
          \node at (v3) {$1$};
          \node at (v4) {$3$};
          \node at (v5) {$4$};
          \node at (v6) {$3$};
          \node at (v7) {$4$};
          \node at (v8) {$2$};
          \node at (v9) {$5$};
          \node at (v10) {$5$};
          % edges
          \draw (v1)--(v2);
          \draw (v1)--(v3);
          \draw (v3)--(v4);
          \draw (v7)--(v8);
          \draw (v6)--(v8);
          \draw (v6)--(v9);
          \draw (v3)--(v5)--(v9)--(v10);
          \node at (2,-3.5) {$u' = \glide\glide$};
        \end{tikzpicture}
    \end{tabular}
    % \end{tabular*}
  }
  \caption{\texttt{ExtendedPG} performed on a glued pair $(\pgseq,\canopy)$.}\label{fig: Weighted PG}
\end{figure}

\section{Linial arrangements and local binary search trees}\label{sec: lbs}
We will now consider the case where $a_2=b_1=0$. 
In the setting outlined in the introduction, this corresponds to considering labeled trees such that they have only weak right ascents and weak left descents. 
We will refer to such labeled trees  as \emph{local binary search trees} (henceforth \emph{LBS trees}) after Stanley. 
The problem of enumerating standard LBS trees was first considered by Postnikov \cite{Postnikov-JCTA}, wherein he showed that these were equinumerous with intransitive trees (or alternating trees). 
Postnikov's interest was in enumerating the number of regions in a well-known deformation of the Coxeter arrangement of type $A$, the \emph{Linial arrangement}, which, for a given $n\in \bP$, is defined to be the arrangement of hyperplanes $x_i-x_j=1$ for $1\leq i<j\leq n$ in $\bR^n$.
We will denote this arrangement by $\mathcal{L}_n$.
We will construct another subset of the set of labeled trees that is equinumerous with LBS trees, and use it to define an action of the symmetric group on the regions of the Linial arrangement. 
It is worth emphasizing that the same subset of trees has been considered by Bernardi \cite{Bernardi} to solve the problem of finding a bijection between Linial regions and LBS trees. 
Furthermore, recall that the analogous question of constructing an $\mathfrak{S}_n$-action on the regions of the Shi arrangement is well-studied and gives rise to the classical parking function representation. 
Our $\mathfrak{S}_n$-action shares a key feature with the parking function representation, that of $h$-positivity. We describe the details next.

\cref{cor: expansion using marked trees} in the case under consideration yields
\begin{align}\label{eqn: h-expansion lbs}
G_n&=\sum_{T\in \lbt_n}(a_1b_2)^{|\biv{T}|}(a_1+b_2)^{|\univ{T}|} h_{\typ{T}}= \sum_{T\in \pbt_n}a_1^{\rightt}b_2^{\leftt} h_{\typ{T}}.
\end{align}
where the second equality follows from  the Foata-Strehl action on trees.
Let $\rightt$ and $\leftt$ denote the number of right edges and left edges in $T$, respectively. Since $\rightt+\leftt=n-1$ for any $T\in \pbt_n$, we can set $b_2=1$. 
We are now ready to describe our $\mathfrak{S}_n$-module whose graded Frobenius characteristic is given by $G_n$.
A \emph{$B$-tree} is defined to be a standard labeled binary tree satisfying the condition that every internal node has a label that is less than the label of its right child, provided it exists. Otherwise, it is less than the label of its left child.

Let $\berntree_n$ denote the set of $B$-trees on $n$ nodes.
Our arguments reveal that the number of standard LBS trees on $n$ nodes is equal to the cardinality of $\berntree_n$. 
Now note that if $T\in \berntree_n$ and  $\pre{T}$ is broken into subwords precisely at the terminal nodes, then each subword is increasing. 
This allows us to define an obvious $\mathfrak{S}_n$-action on $\berntree_n$. 
Given $\sigma\in \mathfrak{S}_n$, we relabel the node labeled $i$ with $\sigma(i)$ and then sort the labels on every subword that contributes to $\pre{T}$ from before. 
This ensures that the resulting tree is still a $B$-tree.


Let $\bC \berntree_n$ denote the vector space generated by formal linear combinations of trees in $\berntree_n$.  
Then clearly $\bC\berntree_n$ is a $\mathfrak{S}_n$-module graded by the number of right edges.

\begin{theorem}
The graded Frobenius characteristic of the $\mathfrak{S}_n$-module $\bC\berntree_n$ is given by
\begin{align*}
\sum_{T\in \pbt_n}a_1^{\rightt}h_{\typ{T}}.
\end{align*}
Using Bernardi's bijection between  $\berntree_n$ and regions of $\mathcal{L}_n$, our action can be lifted to an action of $\mathfrak{S}_n$ on the regions of $\mathcal{L}_n$.
\end{theorem}
The previous theorem gives a new formula for the number of regions in $\mathcal{L}_n$ as $|\berntree_n|=\sum_{T\in\pbt_n}\binom{n}{\typ{T}}$, where for any composition $\alpha=(\alpha_1,\ldots,\alpha_k)\vDash n$ we let $\binom{n}{\alpha}:=\frac{n!}{\alpha_1!\cdots \alpha_k!}$.

We now turn our discussion to another notion of importance both in algebraic combinatorics and discrete geometry, that of $\gamma$-positivity. Postnikov \cite{Postnikov-JCTA} proved a functional equation for the generating function for the distribution of right vertices over the set of intransitive trees. That is, he considered the polynomial $f_n(x)=\sum_{k\geq 1} f_{nk}x^k$ where $f_{nk}$ equals the number of intransitive trees on $[n+1]$ with $k$ right vertices. We refer the reader to \cite{Postnikov-JCTA} for the terminology used herein. By comparing the functional equation in \cite[Theorem 3]{Postnikov-JCTA} with the functional equation for the generating function $B$ in the case under consideration (where $a_2=b_1=0$) we obtain the following result.

\begin{theorem}
  For $n\geq 1$, the number of intransitive trees on $[n+1]$ with $k$ right vertices equals the number of standard local binary search trees on $[n]$ with $k-1$ right descents.
  In particular, the polynomials $f_n(x)$ considered by Postnikov are $\gamma$-positive. Therefore, the sequence of coefficients of $f_n(x)$ is unimodal.
\end{theorem}
The second half of the above theorem follows from Equation \eqref{eqn: h-expansion lbs}.
In fact, we conjecture something stronger; that for all $n\geq 1$, all of the roots of the polynomial $f_n(x)$ are negative real numbers.
This in turn would imply that the coefficients of $f_{n}(x)$ form a \emph{log-concave sequence}.

\iffalse
Then the above discussion implies
\begin{align*}
\sum_{T\in } a_1^{\# \text{ of left edges}}b_2^{\# \text{ of right edges}}=\sum_{T\in \lbt_n} (a_1b_2)^{|X|}(a_1+b_2)^{|Y|} \binom{n}{\alpha(T)}
\end{align*}
In the equality above, the sum on the left runs over the appropriate set of labeled trees while the sum on the right ranges over the appropriate set of unlabeled ones.
\fi

\section{Further avenues}\label{sec: back to the future}

We now turn our attention to the case where exactly one of the variables has been set to $0$. In this case we recover some deformation of the classical parking function representation. This is already implicit in our functional equation, but there is one curious aspect worth emphasizing: Our representation is not $h$-positive. In particular, it cannot be recovered as a graded Frobenius characteristic of the symmetric group action on parking functions or on labeled Dyck paths. It would be interesting to construct an $\mathfrak{S}_n$ representation with the right Frobenius characteristic.

Not included in this extended abstract are two more proofs of \cref{thm: ribbon functional equation}. The first is a generating function proof using Gessel's functional equation combined with a consequence of the Carlitz-Scoville-Vaughan Theorem~\cite{Carlitz-Scoville-Vaughan}. The second involves a lift of Gessel's functional equation for the generating function $S$ in the Hopf algebra of noncommutative symmetric functions defined in the seminal paper \cite{GKLLRT} and utilizes classical techniques to cancel out negative terms via flip equivalence on trees. Indeed, we demonstrate that all of our proofs have natural interpretations in the noncommutative setting.

There is much more to explore in terms of representation theory. In future work, we plan to explore the representation theory behind this Schur positivity phenomena, both from the $\mathfrak{S}_n$ perspective and the $0$-Hecke perspective. Finally, the connections to diagonal harmonics mentioned above and work of Bergeron-Pr\'eville-Ratelle~\cite{FBergeron-Preville-Ratelle} remain to be explored.

\acknowledgements{We are especially grateful to Sara Billey for helpful discussions and remarks. Additionally, the second and third authors would like to thank Patricia Hersh and Jia Huang for helpful correspondence.}

\begingroup\emergencystretch=2em
\printbibliography
\endgroup

\end{document}
